//Given the head of a sorted linked list, delete all nodes that have duplicate n
//umbers, leaving only distinct numbers from the original list. Return the linked 
//list sorted as well. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,3,3,4,4,5]
//Output: [1,2,5]
// 
//
// Example 2: 
//
// 
//Input: head = [1,1,1,2,3]
//Output: [2,3]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [0, 300]. 
// -100 <= Node.val <= 100 
// The list is guaranteed to be sorted in ascending order. 
// 
// Related Topics 链表 
// 👍 625 👎 0


package leetcode.editor.cn;

//Java：Remove Duplicates from Sorted List II
class P82RemoveDuplicatesFromSortedListIi {
    public static void main(String[] args) {
        Solution solution = new P82RemoveDuplicatesFromSortedListIi().new Solution();
        // TO TEST
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        solution.deleteDuplicates(node1);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode dumpyHead = new ListNode(Integer.MIN_VALUE);
            dumpyHead.next = head;
            ListNode cur = head;
            ListNode pre = dumpyHead;
            while (cur != null && cur.next != null) {
                ListNode next = cur.next;
                int curVal = cur.val;
                boolean hasDup = false;
                while (next != null && next.val == curVal) {
                    next = next.next;
                    hasDup = true;
                }
                if (hasDup) {
                    pre.next = next;
                    cur = next;
                } else {
                    pre = cur;
                    cur = next;
                }
            }
            return dumpyHead.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}